User blog:Fejfo/Super Fast Beaver Hierarchies and a weird OCF
This is in no way a new idea but I had never thought about higher order busy beavers as an ordinal hierachy before and it has some intersting implications. Note: I couldn't find a definition of \( \omega^{CK}_\alpha \) I could understand, In this post I assume it is the supremum of all ordinals computable on an order \( -1+\alpha \) machine. Busy Beaver Hierachy Order \( 0n \) turing machine= a 2-symbol, n-state turing machine. Order \( \alphan \) turing machine= a 2-symbol, n-state turing machine with oracles for order \( a \in \alpha\) turing machines. \[ BB_\alpha(n)=\text{the largest output of a halting order $\alphan$ turing machine} \\ \Rightarrow BB_0(n)=BB(n) \] This grows much faster than the fast growing hierachy (\( BB_\alpha\approx f_{\omega^{CK}_{1+\alpha}}\)) but at the cost of uncomputability. You may also notice \( BB_\alpha \) seems to be defined for uncountable ordinals but to explore this fully we need a more formal definition of those oracles. I'll be doing this using the bitf*ck programming language (since I like it more and it's turing complete anyway) Bit Beaver Hierachy Bitf*ck Bitf*ck a variant of Brainf*ck consists of: #A half infinite binary input tape (start in first cell) #6 instructions ##> move to the right on the tape ##< move to the left on the tape (in the first cell this does nothing) ##[ if the current cell is 0 goto the matching ] instruction ##] if the current cell is 1 goto the matching [ instruction ##~ apply the NOT gate to the current cell (0 becomes 1 and vice versa) ##' the oracle instruction, this will be explain later #instructions are excecuted one by one (and counted) until you run out at that moment the program halts and the tape becomes the output. Functions in bitf*ck A program \( F \) is a function \( F(x_1,x_2,...,x_n)=(y_1,y_2,...,y_m) \) if: *when the input consists of \( n \) 1 groups of length \( x_i \) seperated by 0s (starting in the first cell), *the output (after halting) consists of of \( m \) 1 groups of length \( y_i \) seperated by 0s. \( F(x)=y \) is shorthand for \( F(x1)=(y1) \) Lexographical ordering Well-formed bitfuck programs are first indexed alphabetically. And then they are ordered in the following way: *\( Onm=(n,\text{the $m^{th}$ alphabetical program}) \) *the final ordering \( L \) is made by: **takeing the first element of O1 **takeing the next element of O1 and then O2 **takeing the next element of O1,O2,O3 **and so on \( Lx \) denotes the xth program (starting from 1) And \( index(p) \) denotes \( x : Lx=p \) Ordinals in bitf*ck Ordinals are encoded as functions representing their fundamental sequence. \( \alpha(x)=index(\alpha[Lx]) \) The input is the index of an ordinal indicating which element of a fundamental sequence to output (as it's index). When \( x\not\in cf(\alpha) \) the program can output any element of it's fundamental sequence. This means we can define \( \alpha=\sup\{ \alpha(n) : n \in \omega \} \) *zero isn't a program but referenced by with index 0 * 1 is a program like ~> which earses it's input and thus outputs the index 0 * ω is a program which earaes programs not representing finite ordinals The first element of the tuples in the ordering is the index of the ordinal indicating the order of the program. The ' instruction In a program of order \( \alpha \) ' does the following: *let i be the length of the current 1 group (arround the selected cell) *let \( (\beta,p)=Li \) *if \( \beta \not\in \alpha \) or p is a halting order \( \beta \) program the current bit is set to 0 This means ' lets the bit stay 1 if it is able to determine the program halts. Bit Beaver Hierachy Now I can finally define: (The lowercase b is mainly to distinguisch it from BB but it's also a reference to binary.) \[ bB_\alpha(n)=\max\{ \operatorname{steps}(F,0) : F \text{ is a halting (on empty input) order $\alpha$ program with $n$ instructions} \} \] This is actually more like a maximum shifts function, the sum barely has an effect on later values. Finally the OCF It seems like \( bB_\Omega(n) \) is well defined because the length of the program limits it's growth. The same argument could be made for \( bB_{\Omega_\alpha} \) or \( bB_I \) this might break at a certain large cardinal but I'm not sure why that would happen. This means you can define: \[ \psi_{bB}(\alpha)=min\{ β : f_\beta >> bB_\alpha \} \] And \( \psi_{BB}(\alpha)=min\{ β : f_\beta >> BB_\alpha \} \) It's interesting that this seems to collapse with out the use of closure functions so all you need is the definition of the large ordinal which needs to be brought in from above (\( \Omega \) is an order \( \Omega \) program ) which doesn't feel right Analysis? It's unclear to me how fast \( bB_\Omega \) would grow, I think it's limited by which ordinals it can acces. Programs of order \( \alpha \) can define ordinals upto \( \omega^{CK}_{1+\alpha} \) so \( \psi_{bB}(\Omega) \) might be the supremum of a programs with an oracle for \( \alpha \mapsto \omega^{CK}_{\alpha} \) ? This is why I think the way the oracles are encoded is very important. Something else to investigate might be if there are catching points of the beaver hierachies and the fgh, I guess these would be the fixed points of "the alpha-th church-kleene ordinal" So inconclusion I seem to be struggeling to even find notation to analyse this with. A more traditional version of this as a theta OCF might include a set closed under programs with an oracle for previous functions. Maybe something like that could be used for proper analysis. Very early values of \( bB_0 \) [WIP] Problems As P進大好きbot pointed out \( \Omega \) as an order \( \Omega \) program doesn't work because this would mean it's index has to be larger than itself which is a contradiction so there is no program for \( \Omega \) so my notiation is constant for uncountable ordinals. I might be switching to an infinite time version of bitf*ck for this reason. After trying to calculate a few values of \( bB_0 \) I don't like the sum of all stepcounts any more I changeing that now. Category:Blog posts